package leetcode.code1219;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

/**
 * hash是错的，有路径依赖
 *
 * @author CaoYu
 * @date 2022年2月5日
 * @description
 */
public class Solution2 implements IDebug {

	int[][] grid;
	int m, n;

	public int getMaximumGold(int[][] grid) {
		m = grid.length;
		n = grid[0].length;
		this.grid = grid;
		int ans = 0;
		int[] been = new int[m];
		Integer[][] ansHash = new Integer[m][n];
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				int cur = this.start(i, j, been, ansHash);
				ans = Math.max(ans, cur);
				ansHash[i][j] = ans;
			}
		}
		return ans;
	}

	private int f(int i, int j, int[] been, Integer[][] ansHash) {
		int max = this.start(i + 1, j, been, ansHash);
		max = Math.max(max, this.start(i - 1, j, been, ansHash));
		max = Math.max(max, this.start(i, j + 1, been, ansHash));
		max = Math.max(max, this.start(i, j - 1, been, ansHash));
		return max + this.grid[i][j];
	}

	private int start(int i, int j, int[] been, Integer[][] ansHash) {
		if (i < 0 || i >= m || j < 0 || j >= n) {
			return 0;
		}
		if ((been[i] & 1 << j) != 0) {
			return 0;
		}
		if (this.grid[i][j] == 0) {
			been[i] = been[i] | (1 << j);
			return 0;
		}
		if (ansHash[i][j] != null) {
			return ansHash[i][j];
		}
		int temp = been[i];
		been[i] = been[i] | (1 << j);
		int ans = this.f(i, j, been, ansHash);
		been[i] = temp;
		return ans;
	}

	@Override
	public void debug1() {
		HelpDebug.compare(24, this.getMaximumGold(HelpDebug.str2array1("[[0,6,0],[5,8,7],[0,9,0]]")));

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub
		HelpDebug.compare(28, this.getMaximumGold(HelpDebug.str2array1("[[1,0,7],[2,0,6],[3,4,5],[0,3,0],[9,0,20]]")));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution2 so = new Solution2();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
	}

}
